package leetcode.editor.cn;

/**
 * 题目Id：5
 * 题目：最长回文子串
 * 日期：2023-08-21 09:02:42
 */
//给你一个字符串 s，找到 s 中最长的回文子串。
//
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
//
// Related Topics 字符串 动态规划 👍 6724 👎 0


public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        String babad = solution.longestPalindrome("cbbd");
        System.out.println(babad);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome2(String s) {
            String str2 = "";
            for (int i = 0; i < s.length(); i++) {
                for (int j = i; j <= s.length(); j++) {
                    String str = s.substring(i, j);
                    if (isHuiwen(str)) {
                        str2 = str.length() > str2.length() ? str : str2;
                    }
                }
            }
            return str2;
        }

        private boolean isHuiwen(String str) {
            if (str.length() == 0) {
                return true;
            }
            int left = 0, right = str.length() - 1;
            while (left < right) {
                if (str.charAt(left) != str.charAt(right)) {
                    return false;
                }
                left++;
                right--;
            }
            return true;

        }


        /**
         * 1.构建动态规划数组dp，表示s[i..j] 是否是回文串
         * 2.长度为1的子串一定是回文串
         * 3.从长度为2的子串进行遍历，只需要判断首位两个字符是否相等
         * 因为dp[i][j] 只和 dp[i+1][j-1] 有关，所以可以只保存一行
         */
        public String longestPalindrome(String s) {
            int len = s.length();
            if (len < 2) {//字符串长度小于2 一定是回文串
                return s;
            }
            int maxLen = 1;
            int begin = 0;
            // dp[i][j] 表示 s[i..j] 是否是回文串。二维数组一定是下半部计算的；上半部倒过来了，不是s的子串
            boolean[][] dp = new boolean[len][len];
            // 初始化：所有长度为 1 的子串都是回文串
            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
            }
            char[] charArray = s.toCharArray();
            //从长度为2的字串开始
            for (int L = 2; L <= len; L++) {
                // 枚举左边界，左边界的上限设置可以宽松一些
                for (int i = 0; i < len; i++) {
                    int j = L + i - 1;//子串右边界
                    if (j >= len) {//是否越界
                        break;
                    }
                    if (charArray[i] != charArray[j]) {//判断首尾两个字符是否相等
                        dp[i][j] = false;
                    } else {
                        if (L <= 2) {//L<=2,说明只有连个字母
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i + 1][j - 1];//同时向内缩一位
                        }
                    }
                    //判断字串的长度和起始位置
                    if (dp[i][j] && L > maxLen) {
                        maxLen = L;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }

    }

//leetcode submit region end(Prohibit modification and deletion)

}
